# -*- encoding: utf-8 -*-


class BoyerMooreSearch(object):

    def __init__(self, text, pattern):
        self.pattern = pattern
        self.text = text
        self.pattern_len = len(pattern)
        self.text_len = len(text)

    def match_in_pattern(self, char):
        """
        从右到左在pattern查找char的索引位置
        :param char:
        :return:
        存在返回索引，否则返回-1
        """
        for i in range(self.pattern_len - 1, -1, -1):
            if self.pattern[i] == char:
                return i
        return -1

    def mismatch_in_text(self, current_position):
        """
        将匹配模式串和主串的每个字符从右到左
        :param current_position: 当前模式串所在主串最左边字符的位置
        :return:
        如果匹配到不一样的字符，返回不匹配字符在主串中的位置
        如果全部匹配，则返回-1
        """
        for i in range(self.pattern_len - 1, -1, -1):
            if self.pattern[i] != self.text[current_position + i]:
                return current_position + i
        return -1

    def bad_character_heuristic(self):
        """查找模式串在主串的位置并返回位置"""
        position = []
        for i in range(self.text_len - self.pattern_len + 1):
            mismatch_index = self.mismatch_in_text(i)
            if mismatch_index == -1:
                position.append(i)
            else:
                match_index = self.match_in_pattern(self.text[mismatch_index])
                i = mismatch_index - match_index
        return position


if __name__ == '__main__':
    text = "ABAABA"
    pattern = "AB"
    bms = BoyerMooreSearch(text, pattern)
    positions = bms.bad_character_heuristic()

    if len(positions) == 0:
        print("No match found")
    else:
        print("Pattern found in following positions: ")
        print(positions)
